public class Sort {

    //冒泡排序
    //时间复杂度：O(N^2)
    //空间复杂度：O(1)
    //稳定性：稳定
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j + 1]){
                    swap(array,j,j + 1);
                }
            }
        }
    }

    private static void swap(int[] array, int j, int i) {
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }


    //计数排序
    //无需比较的排序
    // N 代表待排序的元素，K 代表数据范围大小
    //时间复杂度：O(N + K)
    //空间复杂度：O(N + K)
    //稳定性：稳定
    public static void countSort(int[] array){
        int[] bucket = new int[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        //此时已经将所有原数组元素记录好
        //打印
        for (int i = 0; i < bucket.length; i++) {
            if(bucket[i] != 0){
                System.out.print(i + " ");
                bucket[i]--;
            }
        }
    }


    //归并排序
    //先分解，再合并
    //时间复杂度：O(N)
    //空间复杂度：O(N)
    //稳定性：稳定
    public static void mergeSort(int[] array){
        merge(array,0,array.length - 1);
    }

    private static void merge(int[] array, int left, int right) {
        if(left >= right) {
            return ;
        }
        //分解
        int mid = (left + right) / 2;
        merge(array,left,mid);
        merge(array,mid + 1,right);
        //合并
        combine(array,left,right,mid);
    }

    private static void combine(int[] array, int left, int right, int mid) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int[] tmp = new int[right - left + 1];
        int k = 0;

        while(s1 <= e1 && s2 <= e2){
            if(array[s1] < array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        while(s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmp[k++] = array[s2++];
        }
        //走到这里相当于 tmp 数组中的元素都有序了
        //接下来将 tmp 数组中的内容拷贝到 array 中
        for (int i = 0; i < k; i++) {
            array[i + left] = tmp[i];
        }
        
    }


}
